Online shopping is popular nowadays. Electronic commerce (or “e-commerce”) merchants strive to improve user experience by minimizing the period for order fulfillment, timed from an order being placed to a package of the order being delivered to the purchaser. One time-consuming portion of the fulfillment process is “last-mile delivery” (the delivery from a transportation hub to a final destination). For an urban area with high population density, the last-mile delivery may be especially challenging because of high delivery demands, high labor costs, stringent promised delivery time, complicated traffic regulations, and rapid-changing road conditions.
Conventional methods for delivery route planning in urban areas typically rely on experienced delivery workers, such as truck drivers. A driver may have to drive the same route for 3-5 years to discover an efficient route. Conventional back-end computer systems for route planning may have insufficient capability to internalize such experience in route planning. Also, such discovered routes are generally “inflexible”—that is, the conventional back-end systems may have difficulty adjusting them according to changing delivery conditions, which may lead to a load balance problem. For example, when some destinations of a discovered route have an unusually high demand on some day, the driver of that route may be overburdened, while drivers of other routes may be underutilized. However, conventional back-end systems may not optimize in adaptively rearranging the assignments of the drivers to handle this problem.
Another challenge in delivery route planning is restoration—that is, sorting packages in a carrier vehicle to optimize space utilization. Typically, the order of visiting the destinations would affect the restoration. For example, packages for delivery or picked up would be dropped off in a reverse order of storing them. That would be difficult to adjust their location and placement. The restoration problem is correlated with the delivery route planning problem, on which the conventional back-end systems have difficulty to handle with adaptiveness.
Some delivery route planning methods try to treat the problem as a Traveling Salesman Problem (TSP) and seek an approximate solution thereto. The goal of solving TSP is to minimize the time duration for a delivery worker (similar to the “traveling salesman”) to visit all the destinations. However, conventional back-end systems are not optimized to factor some task characteristics or conditions in package delivery or pickup into the TSP solutions, such as that a right turn is easier than a left turn, parking difficulty levels of parking spots, driving accessibility of a neighborhood, driving time for U-turns, or the like.
Therefore, there is a need for efficient, dynamic route planning for e-commerce fulfillment.